package com.datastructure.test.surroundedarea;

public class SurroundedArea {

    public static void main(String[] args) {

    }

    public char[][] surroundedArea (char[][] board) {
        // write code here
        int n=board.length;    // n行
        int m=board[0].length; // m列
        // 最外层的'O'先标记为'A'，能和最外层直接相连的'O'也标记为'A'
        for(int i=0;i<n;i++){
            dfs(board,i,0);  // 左边界
            dfs(board,i,m-1); // 右边界
        }
        for(int j=0;j<m;j++){
            dfs(board,0,j); // 上边界
            dfs(board,n-1,j); // 下边界
        }
        // 遍历整个矩阵，把'O'变为'X', 把'A'变为'O'
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]=='O')
                    board[i][j]='X';
                if(board[i][j]=='A')
                    board[i][j]='O';
            }
        }
        return board;

    }

    void dfs(char[][] board, int x, int y){
        // 不能超出边界
        // 注意最后一个条件不能写成board[x][y]=='X'，会进入死循环
        if(x<0||x>=board.length||y<0||y>=board[0].length||board[x][y]!='O')
            return;
        // 遇到O就改为A
        if(board[x][y]=='O')
            board[x][y]='A';  // 标记为A
        dfs(board,x-1,y);  //上
        dfs(board,x,y+1);  //右
        dfs(board,x+1,y);  //下
        dfs(board,x,y-1);  //左
    }
}
